package leetCode;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

public class T28 {
    public static void main(String[] args) {

        System.out.println(new SolutionT28().strStr("mississippi",
                "issip"));
    }
}
class SolutionT28 {
    public int strStr(String haystack, String needle) {
        int[] next = geyNextArray(needle);
        char[] haystackChars = haystack.toCharArray();
        char[] needleChars = needle.toCharArray();

        int j=0;
        for (int i=0;i<haystack.length();i++){
            while (j>0&&needleChars[j]!=haystackChars[i]){
                j=next[j-1];
            }
            if (needleChars[j]==haystackChars[i]){
                j++;
            }
            if (j==needle.length())return i-needle.length()+1;
        }
        return -1;
    }
    public int[]geyNextArray(String needle){
        char[] chars = needle.toCharArray();
        int [] ret=new int[needle.length()];
        ret[0]=0;
        int j=0;
        for (int i=1;i<needle.length();i++){
            while (j>0&&chars[i]!=chars[j]){
                j=ret[j-1];
            }
            if (chars[j]==chars[i]){
                j++;
            }
            ret[i]=j;
        }
        return ret;
    }
}